00100	begin
00200	comment This is a sort procedure and its test program.  The
00300	number of exchange operations is bounded by
00400			n(log ((max - min)/d)))
00500	where  n  is the number of elements in the array,
00600	max  and  min  are the maximum and minimum
00700	elements respectively and  d  is the smallest difference
00800	between distinct elements of the array.  The present 
00900	version works for integer arrays.;
01000	
01100	comment Here is the sort procedure.;
01200	procedure sort(integer array a); begin
01300	recursive procedure sorta(integer k,l;integer array a);
01400	begin integer min, max,mid,j,m,n; label p,q,r;
01500	if k=l then return;
01600	if k+1=l then begin if a[k]>a[l] then a[k]↔a[l]; return end;
01700	
01800	min←max←a[k];
01900	for j←k+1 step 1 until l do begin
02000	if a[j]<min then min←a[j];
02100	if a[j]>max then max←a[j] end;
02200	if min=max then return;
02300	
02400	mid←(min+max)/2; m←k; n←l;
02500	p:
02600	if m≥n then go to r; if a[n]>mid then
02700		begin n←n-1; go to p end;
02800	q:
02900	if m≥n then go to r; if  a[m]≤mid then
03000		begin m←m+1; go to q end;
03100	a[m]↔a[n]; m←m+1; n←n-1; go to p;
03200	r:
03300	sorta(k,m,a); if m≠l then sorta(m+1,l,a); return end;
03400	sorta(arrinfo(a,1),arrinfo(a,2),a) end;
03500	
03600	comment Here is the test program.;
03700	integer ll; outstr("ll="); ll←cvd(inchwl);
03800	begin integer array b[1:ll]; integer jj;
03900	outstr("Enter the array b.
04000	");
04100	for jj←1 step 1 until ll do b[jj]←cvd(inchwl);
04200	sort(b);
04300	for jj←1 step 1 until ll do outstr(" "&cvs(b[jj])) end;
04400	end;